//
//  ProblemOffer56-1.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/15.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 56 - I. 数组中数字出现的次数 ✅
 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 示例 1：
     输入：nums = [4,1,4,6]
     输出：[1,6] 或 [6,1]
 示例 2：
     输入：nums = [1,2,10,4,1,4,3,3]
     输出：[2,10] 或 [10,2]
 限制：2 <= nums.length <= 10000
 */
@objcMembers class ProblemOffer56_1: NSObject {
    func solution() {
        print(singleNumbers([4,1,4,6]))
        print(singleNumbers([1,2,10,4,1,4,3,3]))
    }
    
    /*
     异或：
     1> 相同的数字异或==0 1^1=0, 0^0=0
     2> 不同的数字异或==1 1^0=1, 1^0=1
     
     1: 遍历数组，对全体数组里的数字进行异或，得到的值result就是： 那2个数字的异或，因为其他都是成对存在，异或后==0
     2: 我们看看result的二进制里面，哪位是1，因为这位是1:说明这2个数字在这位是不同的
     3: 数组中每个数在这一位都是不同的，那么遍历一遍数组：把这一位是1的放到一块，是0的放到一块，这样这2个数字就分开了
     4: 然后把是1的都异或一遍，就得到第一个数，因为是1的集合里面，处理这个数之外，其他都是成对存在的
     5: 是0的也都异或一遍，得到第二个数
     */
    func singleNumbers(_ nums: [Int]) -> [Int] {
        // 1: 全体成员执行一遍 异或；得到的结果reuslt == 这2个数的异或
        var result = 0
        for n in nums {
            result ^= n
        }
        
        // 2: 寻找reuslt里面 二进制 是1的位
        var i = 1
        while (result & i) == 0 {       // 执行 & 操作，如果 == 0 说明 是 0 & 1 = 0， == 1 是：1 & 1 = 0
            i <<= 1
        }
        
        // 3: 遍历数组，把数组的每个数根据 i 这一位是0还是1进行分割，
        var f = 0, s = 0
        for n in nums {
            if n & i == 0 {
                s ^= n
            } else {
                f ^= n
            }
        }
        
        return [f, s]
    }
}
